/* 
 * Copyright (c) 2012 JSquirrelEngine
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in 
 * the Software without restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the
 * Software, and to permit persons to whom the Software is furnished to do so, subject
 * to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
 * OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 * 
 */

package org.jsquirrel.map.impl;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

import org.jsquirrel.geometry.BoundingArea;
import org.jsquirrel.geometry.Polygon;
import org.jsquirrel.geometry.PolygonFactory;
import org.jsquirrel.geometry.PolygonTypes;
import org.jsquirrel.geometry.UnsupportedBoundingIntersectionException;
import org.jsquirrel.geometry.impl.BoundingCircle;
import org.jsquirrel.map.NodeOutOfSpaceBoundsException;
import org.jsquirrel.map.Space2D;
import org.jsquirrel.map.Space2DKeyGenerator;
import org.jsquirrel.map.Space2DNode;
import org.jsquirrel.map.Space2DNodeIntersectionListener;
import org.jsquirrel.map.Space2DNodeIntersectionResult;
import org.jsquirrel.math.F2Vector;
import org.jsquirrel.math.Transform2D;


/**
 * Implementation of {@link Space2D}. The space is represented as a regular grid where 
 * 
 * @author Juan David Adarve Bermudez
 *
 * @param <K> node key, it must be an implementation of {@link Comparable}
 * @param <O> node pay load
 */
public class GridSpace2D<K extends Comparable<K>, O> extends Space2D<K, O> {
	
	
	//*********************************************************************************************
	// INSTANCE ATTRIBUTES
	//*********************************************************************************************
	
	private ArrayList<GridSpace2DNode<K, O>> [][] gridSpace;
	
	private TreeSet<GridSpace2DNode<K, O>> nodesTree;
	
	private TreeSet<GridSpace2DNode<K, O>> limboList;
	
	private float cellWidth, cellHeight;
	
	private int numCellsX, numCellsY;
	
	// Intersection listeners
	
	private ArrayList<Space2DNodeIntersectionListener<K, O>> intersectionListeners;
	
	
	//*********************************************************************************************
	// CONSTRUCTORS
	//*********************************************************************************************
	
	public GridSpace2D(Space2DKeyGenerator<K> kGenerator, Comparator<K> kComparator) {
		super(kGenerator);
		cellWidth = 1;
		cellHeight = 1;
		
		instanciateGrid();
		
		nodesTree = new TreeSet<GridSpace2DNode<K, O>>();
		limboList = new TreeSet<GridSpace2DNode<K, O>>();
		intersectionListeners = new ArrayList<Space2DNodeIntersectionListener<K, O>>();
	}
	
	public GridSpace2D(float x0, float y0, float width, float height, float cellWidth, float cellHeight,
			Space2DKeyGenerator<K> kGenerator) {
		
		super(x0, y0, width, height, kGenerator);
		
		this.cellWidth = cellWidth;
		this.cellHeight = cellHeight;
		
		instanciateGrid();
		
		nodesTree = new TreeSet<GridSpace2DNode<K, O>>();
		limboList = new TreeSet<GridSpace2DNode<K, O>>();
		intersectionListeners = new ArrayList<Space2DNodeIntersectionListener<K, O>>();
	}
	
	//*********************************************************************************************
	// PUBLIC METHODS
	//*********************************************************************************************
	
	public float getCellWidth() {
		return cellWidth;
	}
	
	public float getCellHeight() {
		return cellHeight;
	}
	
	public int getNumCellsX() {
		return numCellsX;
	}
	
	public int getNumCellsY() {
		return numCellsY;
	}
	
	public boolean cellOccupiedByIndex(int xIndex, int yIndex) {
		
		if(xIndex < 0 || xIndex > numCellsX || yIndex < 0 || yIndex > numCellsY) {
			throw new IndexOutOfBoundsException("GridSpace2D.cellOccupiedByIndex(int, int): index out of bounds: (" + xIndex + ", " + yIndex + ")");
		}
		
		return gridSpace[xIndex][yIndex].size() != 0;
	}
	
	@Override
	public void addIntersectionListener(Space2DNodeIntersectionListener<K, O> listener) {
		
		intersectionListeners.add(listener);
	}

	@Override
	public Space2DNode<K, O> createNode(Polygon p) {
		
		if(p == null) {
			throw new NullPointerException("GridSpace2D.createNode(): null Polygon to create node");
		}
		
		if(this.keyGenerator == null) {
			throw new NullPointerException("GridSpace2D.createNode(): null KeyGenerator. First set generator by calling setKeyGenerator()");
		}
		
		GridSpace2DNode<K, O> node = new GridSpace2DNode<K, O>(p, this.keyGenerator.generateKey());
		return node;
	}

	@Override
	public void insertNode(Space2DNode<K, O> node) throws NodeOutOfSpaceBoundsException {
		
		if(node == null) {
			return;
		}
		
		if(!(node instanceof GridSpace2DNode<?, ?>)) {
			
			throw new IllegalArgumentException("GridSpace2D.insertNode(): this implementation only allows instances of GridSpace2DNode");
		}
		
		
		GridSpace2DNode<K, O> gridNode = (GridSpace2DNode<K, O>)node;
		Polygon p = gridNode.getPolygon();
		
		if(!p.intersectsRectangle(x0, y0, width, height)) {
			throw new NodeOutOfSpaceBoundsException("Node is out of space boundaries: Polygon: " + p);
		}
		
		TreeSet<GridSpace2DNode<K, O>> intersectionSet = new TreeSet<GridSpace2DNode<K, O>>();
		
		//INSERTION OF THE NODE ACCORDING TO THE BOUNDING AREA IT HAS
		BoundingArea bArea = p.getBoundingArea();		
		if(bArea == null) {
			
			insertPolygonNoBoundingArea((GridSpace2DNode<K, O>)node, intersectionSet);
		}
		else {
			
			switch(bArea.type()) {
			
			case BOUNDING_CIRCLE:
				insertPolygonBoundingCircle((GridSpace2DNode<K, O>)node, intersectionSet);
				break;
				
			case BOUNDING_RECTANGLE:
				insertPolygonBoundingRectangle((GridSpace2DNode<K, O>)node, intersectionSet);
				break;
				
			default:
				throw new RuntimeException("BoundingArea not supported by GridSpace2D. Type: " + bArea.type());
			}
		}
		
		// INSERTION ON NodesTree
		this.nodesTree.add(gridNode);
		
		// CHECKING FOR INTERSECTION EVENTS
		Iterator<GridSpace2DNode<K, O>> it = intersectionSet.iterator();
		while(it.hasNext()) {
			
			GridSpace2DNode<K, O> itNode = it.next();
			Space2DNodeIntersectionResult result = gridNode.checkIntersection(itNode);
			if(result != Space2DNodeIntersectionResult.NO_INTERSECTION) {
				
				fireIntersectionEvent((GridSpace2DNode<K, O>)node, itNode, result);
			}
		}
		
		
		// set the limbo flag of the node as false (node is at grid)
		((GridSpace2DNode<K, O>)node).setLimboFlag(false);
	}

	@Override
	public boolean removeNode(K key) {
		
		GridSpace2DNode<K, O> node = (GridSpace2DNode<K, O>)queryByKey(key);
		if(node == null) {
			return false;
		}
		
		// remove the node from nodesTree
		nodesTree.remove(node);
		
		// if the node is at the limbo
		if(node.atLimbo()) {
			
			return limboList.remove(node);
		}
		else {
			
			Polygon p = node.getPolygon();
			BoundingArea bArea = p.getBoundingArea();
			
			if(bArea == null) {
				return removePolygonNoBoundingArea(node);
			} else {
				
				switch(bArea.type()) {
				
				case BOUNDING_RECTANGLE:
					return removePolygonBoundingRectangle(node);
				
					
				case BOUNDING_CIRCLE:
					return removePolygonBoundingCircle(node);
					
					
				default:
					//TODO remove the polygon as without bounding volume? or raise an exception
					return false;
				}
			}
		}
	}

	@Override
	public Space2DNode<K, O> queryByKey(K key) {
		
		GridSpace2DNode<K, O> node = nodesTree.ceiling(new GridSpace2DNode<K, O>(PolygonFactory.create(PolygonTypes.ARRAY_POLYGON), key));
		
		if(node == null) {
			return null;
		}
		
		if(node.getKey().compareTo(key) == 0) {
			return node;
		}
		
		return null;
	}

	@Override
	public Iterable<Space2DNode<K, O>> queryByRectangle(float x, float y, float width,
			float height) {
		
		TreeSet<Space2DNode<K, O>> returnSet = new TreeSet<Space2DNode<K, O>>();
		
		// index for the bounding rectangle inside the grid
		int xi = Math.max((int)Math.floor((x - x0)/cellWidth), 0);
		int yi = Math.max((int)Math.floor((y - y0)/cellHeight) , 0);
		
		int xf = Math.min((int)Math.floor((x + width - x0)/cellWidth) + 1, numCellsX);
		int yf = Math.min((int)Math.floor((y + height - y0)/cellHeight) + 1, numCellsY);
		
		
		for(int i = xi; i < xf; i ++) {
			for(int j = yi; j < yf; j ++) {
				
				ArrayList<GridSpace2DNode<K, O>> list = gridSpace[i][j];
				
				Iterator<GridSpace2DNode<K, O>> it = list.iterator();
				while(it.hasNext()) {					
					returnSet.add(it.next());
				}
				
			}
		}
		
		return returnSet;
	}

	@Override
	public Iterable<Space2DNode<K, O>> queryByPolygon(Polygon p) {
		
		TreeSet<Space2DNode<K, O>> returnSet = new TreeSet<Space2DNode<K,O>>();
		
				
		F2Vector bLeft = new F2Vector();
		F2Vector uRight = new F2Vector();
		
		p.getBoundingRectangle(bLeft, uRight);
		
		// index for the bounding rectangle inside the grid
		int xi = Math.max((int)Math.floor((bLeft.x() - x0)/cellWidth), 0);
		int yi = Math.max((int)Math.floor((bLeft.y() - y0)/cellHeight) , 0);
		
		int xf = Math.min((int)Math.floor((uRight.x() - x0)/cellWidth) + 1, numCellsX);
		int yf = Math.min((int)Math.floor((uRight.y() - y0)/cellHeight) + 1, numCellsY);

		// this is to assure that at least one cell is iterated
		xi = xi == xf && xf == numCellsX ? Math.max(xi - 1, 0) : xi;
		yi = yi == yf && yf == numCellsY ? Math.max(yi -1, 0) : yi;
		
		for(int i = xi; i < xf; i ++) {
			for(int j = yi; j < yf; j ++) {
				
				// if the Polygon intersects the rectangle that represents the cell of the (i, j) of the grid,
				// then the node shall be inserted on this cell
				if(p.intersectsRectangle(i*cellWidth, j*cellHeight, cellWidth, cellHeight)) {
				
					ArrayList<GridSpace2DNode<K, O>> list = gridSpace[i][j];
					
					// iterates over the elements on the list and add them to the set to check intersections
					Iterator<GridSpace2DNode<K, O>> it = list.iterator();
					while(it.hasNext()) {
						returnSet.add(it.next());
					}
					
				}
			}
		}
		
		return returnSet;
	}
	
	@Override
	public boolean putOnLimboByKey(K key) {
		
		GridSpace2DNode<K, O> node = (GridSpace2DNode<K, O>)queryByKey(key);
		if(node == null) {
			return false;
		}		
		
		// if the node is at the limbo
		if(node.atLimbo()) {
			
			return true;
		}
		else {
			
			Polygon p = node.getPolygon();
			BoundingArea bArea = p.getBoundingArea();
			
			boolean removingFromGrid = false;
			
			if(bArea == null) {
				removingFromGrid = removePolygonNoBoundingArea(node);
			} else {
				
				switch(bArea.type()) {
				
					case BOUNDING_RECTANGLE:
						removingFromGrid = removePolygonBoundingRectangle(node);
						break;
						
					case BOUNDING_CIRCLE:
						removingFromGrid = removePolygonBoundingCircle(node);
						break;
						
					default:
						//TODO remove the polygon as without bounding volume? or raise an exception
						removingFromGrid = false;
						break;
				}
			}
			
			if(removingFromGrid) {
				node.setLimboFlag(true);
				limboList.add(node);
				return true;
			}
		}
		
		return false;
	}

	@Override
	public boolean putOnLimboByRectangle(float x, float y, float width,
			float height) {
		
		
		// tells if at least one node has gone to limbo area
		boolean oneInsertedOnLimbo = false;
		
		// index for the bounding rectangle inside the grid
		int xi = Math.max((int)Math.floor((x - x0)/cellWidth), 0);
		int yi = Math.max((int)Math.floor((y - y0)/cellHeight) , 0);
		
		int xf = Math.min((int)Math.floor((x + width - x0)/cellWidth) + 1, numCellsX);
		int yf = Math.min((int)Math.floor((y + height - y0)/cellHeight) + 1, numCellsY);
		
		
		for(int i = xi; i < xf; i ++) {
			for(int j = yi; j < yf; j ++) {
				
				ArrayList<GridSpace2DNode<K, O>> list = gridSpace[i][j];
				
				Iterator<GridSpace2DNode<K, O>> it = list.iterator();
				while(it.hasNext()) {
					GridSpace2DNode<K, O> node = it.next();
					node.setLimboFlag(true);
					limboList.add(node);
					oneInsertedOnLimbo = true;
				}
				
				// clears the list from all objects that were put at limbo
				list.clear();
			}
		}
		
		return oneInsertedOnLimbo;
	}

	@Override
	public boolean putOnLimboByPolygon(Polygon p) {
		
		boolean oneInsertedOnLimbo = false;
		
		F2Vector bLeft = new F2Vector();
		F2Vector uRight = new F2Vector();
		
		p.getBoundingRectangle(bLeft, uRight);
		
		// index for the bounding rectangle inside the grid
		int xi = Math.max((int)Math.floor((bLeft.x() - x0)/cellWidth), 0);
		int yi = Math.max((int)Math.floor((bLeft.y() - y0)/cellHeight) , 0);
		
		int xf = Math.min((int)Math.floor((uRight.x() - x0)/cellWidth) + 1, numCellsX);
		int yf = Math.min((int)Math.floor((uRight.y() - y0)/cellHeight) + 1, numCellsY);

		// this is to assure that at least one cell is iterated
		xi = xi == xf && xf == numCellsX ? Math.max(xi - 1, 0) : xi;
		yi = yi == yf && yf == numCellsY ? Math.max(yi -1, 0) : yi;
		
		for(int i = xi; i < xf; i ++) {
			for(int j = yi; j < yf; j ++) {
				
				// if the Polygon intersects the rectangle that represents the cell of the (i, j) of the grid,
				// then the node shall be inserted on this cell
				if(p.intersectsRectangle(i*cellWidth, j*cellHeight, cellWidth, cellHeight)) {
				
					ArrayList<GridSpace2DNode<K, O>> list = gridSpace[i][j];
					
					// iterates over the elements on the list and add them to the set to check intersections
					Iterator<GridSpace2DNode<K, O>> it = list.iterator();
					while(it.hasNext()) {
						GridSpace2DNode<K, O> node = it.next();
						node.setLimboFlag(true);
						limboList.add(node);
					}
					
					list.clear();
					
				}
			}
		}
		
		return oneInsertedOnLimbo;

	}
	
	@Override
	public void clearLimbo() {
		
		Iterator<GridSpace2DNode<K, O>> it = limboList.iterator();
		while(it.hasNext()) {
			// removes every node from the nodesTree indicating that those node
			// are no longer part of the grid nor the limbo area
			nodesTree.remove(it.next());
		}
		
		limboList.clear();
	}

	@Override
	public void updateLimbo(Transform2D t) {
		
		Iterator<GridSpace2DNode<K, O>> it = limboList.iterator();
		while(it.hasNext()) {
			
			GridSpace2DNode<K, O> node = it.next();
			node.getPolygon().transform(t);
		}
	}

	@Override
	public void flushLimbo() {
		
		Iterator<GridSpace2DNode<K, O>> it = limboList.iterator();
		while(it.hasNext()) {
			
			GridSpace2DNode<K, O> node = it.next();
			node.setLimboFlag(false);
			
			try {
				insertNode(node);
				// removes this node from limbo
				it.remove();
			} catch (NodeOutOfSpaceBoundsException e) {
				// do nothing, this node remains at limbo
			}
		}
	}
	
	@Override
	public String toString() {
		
		StringBuffer buffer = new StringBuffer("GridSpace2D.toString()\n");
		
		buffer.append("GRID\n\n");
		
		
		for(int x = 0; x < numCellsX; x ++) {
			for(int y = 0; y < numCellsY; y ++) {
				
				buffer.append("cell [" + x + ", " + y + "](" + (x0 + x*cellWidth) + ", " + (y0 + y*cellHeight) +  "):");
				
				ArrayList<GridSpace2DNode<K, O>> list = gridSpace[x][y];
				Iterator<GridSpace2DNode<K, O>> it = list.iterator();
				while(it.hasNext()) {
					
					GridSpace2DNode<K, O> node = it.next();
					buffer.append(node + ", ");
				}
				
				buffer.append("\n");
			}
		}
		
		buffer.append("\nLIMBO\n\n");
		
		Iterator<GridSpace2DNode<K, O>> it = limboList.iterator();
		while(it.hasNext()) {
			
			buffer.append(it.next() + "\n");
		}
		
		return buffer.toString();
	}
	
	
	
	//*********************************************************************************************
	// PRIVATE METHODS
	//*********************************************************************************************
	
	@SuppressWarnings("unchecked")
	private void instanciateGrid() {		
		
		numCellsX = (int)Math.ceil(this.width / this.cellWidth);
		numCellsY = (int)Math.ceil(this.height / this.cellHeight);
		
		gridSpace = (ArrayList<GridSpace2DNode<K, O>>[][])Array.newInstance(ArrayList.class, new int[]{numCellsX, numCellsY});
		
		// instanciate every ArrayList in the grid
		for(int i = 0; i < numCellsX; i ++) {
			for(int j = 0; j < numCellsY; j ++) {
				
				gridSpace[i][j] = new ArrayList<GridSpace2DNode<K, O>>();
			}
		}
	}
	
	
	private void insertPolygonNoBoundingArea(GridSpace2DNode<K, O> node, TreeSet<GridSpace2DNode<K, O>> intersectionSet) {
		
		Polygon p = node.getPolygon();
		
		F2Vector bLeft = new F2Vector();
		F2Vector uRight = new F2Vector();
		
		p.getBoundingRectangle(bLeft, uRight);
		
		// index for the bounding rectangle inside the grid
		int xi = Math.max((int)Math.floor((bLeft.x() - x0)/cellWidth), 0);
		int yi = Math.max((int)Math.floor((bLeft.y() - y0)/cellHeight) , 0);
		
		int xf = Math.min((int)Math.floor((uRight.x() - x0)/cellWidth) + 1, numCellsX);
		int yf = Math.min((int)Math.floor((uRight.y() - y0)/cellHeight) + 1, numCellsY);

		// this is to assure that at least one cell is iterated
		xi = xi == xf && xf == numCellsX ? Math.max(xi - 1, 0) : xi;
		yi = yi == yf && yf == numCellsY ? Math.max(yi -1, 0) : yi;
		
		for(int i = xi; i < xf; i ++) {
			for(int j = yi; j < yf; j ++) {
				
				// if the Polygon intersects the rectangle that represents the cell of the (i, j) of the grid,
				// then the node shall be inserted on this cell
				if(p.intersectsRectangle(i*cellWidth, j*cellHeight, cellWidth, cellHeight)) {
				
					ArrayList<GridSpace2DNode<K, O>> list = gridSpace[i][j];
					
					// iterates over the elements on the list and add them to the set to check intersections
					Iterator<GridSpace2DNode<K, O>> it = list.iterator();
					while(it.hasNext()) {
						GridSpace2DNode<K, O> n = it.next();
						intersectionSet.add(n);
					}
					
					// insert the new node on the list
					list.add(node);
				}
				
			}
		}		
		
	}
	
	
	private void insertPolygonBoundingRectangle(GridSpace2DNode<K, O> node, TreeSet<GridSpace2DNode<K, O>> intersectionSet) {
		
		Polygon p = node.getPolygon();
		
		F2Vector bLeft = new F2Vector();
		F2Vector uRight = new F2Vector();
		
		p.getBoundingRectangle(bLeft, uRight);
		
		// index for the bounding rectangle inside the grid
		int xi = Math.max((int)Math.floor((bLeft.x() - x0)/cellWidth), 0);
		int yi = Math.max((int)Math.floor((bLeft.y() - y0)/cellHeight) , 0);
		
		int xf = Math.min((int)Math.floor((uRight.x() - x0)/cellWidth) + 1, numCellsX);
		int yf = Math.min((int)Math.floor((uRight.y() - y0)/cellHeight) + 1, numCellsY);
		
		
		for(int i = xi; i < xf; i ++) {
			for(int j = yi; j < yf; j ++) {
				
				// there is no need to check if the Polygon intersect the grid cell since a bounding
				// rectangle is being used and the values (xi, yi) (xf, yf) tells exactly on which
				// cells the rectangle is
				
				ArrayList<GridSpace2DNode<K, O>> list = gridSpace[i][j];
				
				// iterates over the elements on the list and add them to the set to check intersections
				Iterator<GridSpace2DNode<K, O>> it = list.iterator();
				while(it.hasNext()) {
					GridSpace2DNode<K, O> n = it.next();
					intersectionSet.add(n);
				}
				
				// insert the new node on the list
				list.add(node);
				
				
			}
		}
	}
	
	private void insertPolygonBoundingCircle(GridSpace2DNode<K, O> node, TreeSet<GridSpace2DNode<K, O>> intersectionSet) {
		
		Polygon p = node.getPolygon();
		BoundingCircle circle = (BoundingCircle)p.getBoundingArea();
		
		F2Vector bLeft = new F2Vector();
		F2Vector uRight = new F2Vector();
		
		p.getBoundingRectangle(bLeft, uRight);
		
		// index for the bounding rectangle inside the grid
		int xi = Math.max((int)Math.floor((bLeft.x() - x0)/cellWidth), 0);
		int yi = Math.max((int)Math.floor((bLeft.y() - y0)/cellHeight) , 0);
		
		int xf = Math.min((int)Math.floor((uRight.x() - x0)/cellWidth) + 1, numCellsX);
		int yf = Math.min((int)Math.floor((uRight.y() - y0)/cellHeight) + 1, numCellsY);
		
		
		for(int i = xi; i < xf; i ++) {
			for(int j = yi; j < yf; j ++) {
				
				try {
					
					// if the BoundingCircle intersects the rectangle that represents the cell of the (i, j) of the grid,
					// then the node shall be inserted on this cell
					if(circle.intersectsRectangle(i*cellWidth, j*cellHeight, cellWidth, cellHeight)) {
					
						ArrayList<GridSpace2DNode<K, O>> list = gridSpace[i][j];
						
						// iterates over the elements on the list and add them to the set to check intersections
						Iterator<GridSpace2DNode<K, O>> it = list.iterator();
						while(it.hasNext()) {
							GridSpace2DNode<K, O> n = it.next();
							intersectionSet.add(n);
						}
						
						// insert the new node on the list
						list.add(node);
					}
				}				
				catch(UnsupportedBoundingIntersectionException e) {
					// nothing to do, BoundingCircle supports the intersectsRectangle() method
				}
				
			}
		}
	}
	
	
	private boolean removePolygonNoBoundingArea(GridSpace2DNode<K, O> node) {
		
		Polygon p = node.getPolygon();
		
		F2Vector bLeft = new F2Vector();
		F2Vector uRight = new F2Vector();
		
		p.getBoundingRectangle(bLeft, uRight);
		
		// index for the bounding rectangle inside the grid
		int xi = Math.max((int)Math.floor((bLeft.x() - x0)/cellWidth), 0);
		int yi = Math.max((int)Math.floor((bLeft.y() - y0)/cellHeight) , 0);
		
		int xf = Math.min((int)Math.floor((uRight.x() - x0)/cellWidth) + 1, numCellsX);
		int yf = Math.min((int)Math.floor((uRight.y() - y0)/cellHeight) + 1, numCellsY);

		// This is to correct
		xi = xi == xf && xf == numCellsX ? xi - 1 : xi;
		yi = yi == yf && yf == numCellsY ? yi -1 : yi;
		
		boolean result = false;
		for(int i = xi; i < xf; i ++) {
			for(int j = yi; j < yf; j ++) {
				
				// if the Polygon intersects the rectangle that represents the cell of the (i, j) of the grid,
				// then the node shall be inserted on this cell
				if(p.intersectsRectangle(i*cellWidth, j*cellHeight, cellWidth, cellHeight)) {
				
					ArrayList<GridSpace2DNode<K, O>> list = gridSpace[i][j];
					result |= list.remove(node);

				}
				
			}
		}
		
		return result;
	}
	
	private boolean removePolygonBoundingRectangle(GridSpace2DNode<K, O> node) {
	
		Polygon p = node.getPolygon();
		
		F2Vector bLeft = new F2Vector();
		F2Vector uRight = new F2Vector();
		
		p.getBoundingRectangle(bLeft, uRight);
		
		// index for the bounding rectangle inside the grid
		int xi = Math.max((int)Math.floor((bLeft.x() - x0)/cellWidth), 0);
		int yi = Math.max((int)Math.floor((bLeft.y() - y0)/cellHeight) , 0);
		
		int xf = Math.min((int)Math.floor((uRight.x() - x0)/cellWidth) + 1, numCellsX);
		int yf = Math.min((int)Math.floor((uRight.y() - y0)/cellHeight) + 1, numCellsY);
		
		boolean result = false;
		for(int i = xi; i < xf; i ++) {
			for(int j = yi; j < yf; j ++) {
				
				// there is no need to check if the Polygon intersect the grid cell since a bounding
				// rectangle is being used and the values (xi, yi) (xf, yf) tells exactly on which
				// cells the rectangle is
				
				ArrayList<GridSpace2DNode<K, O>> list = gridSpace[i][j];
				result |= list.remove(node);
			}
		}
		
		return result;
	}
	
	private boolean removePolygonBoundingCircle(GridSpace2DNode<K, O> node) {
		
		Polygon p = node.getPolygon();
		BoundingCircle circle = (BoundingCircle)p.getBoundingArea();
		
		F2Vector bLeft = new F2Vector();
		F2Vector uRight = new F2Vector();
		
		p.getBoundingRectangle(bLeft, uRight);
		
		// index for the bounding rectangle inside the grid
		int xi = Math.max((int)Math.floor((bLeft.x() - x0)/cellWidth), 0);
		int yi = Math.max((int)Math.floor((bLeft.y() - y0)/cellHeight) , 0);
		
		int xf = Math.min((int)Math.floor((uRight.x() - x0)/cellWidth) + 1, numCellsX);
		int yf = Math.min((int)Math.floor((uRight.y() - y0)/cellHeight) + 1, numCellsY);
		
		boolean result = false;
		for(int i = xi; i < xf; i ++) {
			for(int j = yi; j < yf; j ++) {
				
				try {
					
					// if the BoundingCircle intersects the rectangle that represents the cell of the (i, j) of the grid,
					// then the node shall be inserted on this cell
					if(circle.intersectsRectangle(i*cellWidth, j*cellHeight, cellWidth, cellHeight)) {
					
						ArrayList<GridSpace2DNode<K, O>> list = gridSpace[i][j];
						result |= list.remove(node);
					}
				}				
				catch(UnsupportedBoundingIntersectionException e) {
					// nothing to do, BoundingCircle supports the intersectsRectangle() method
				}
				
			}
		}
		
		return result;
	}


	private void fireIntersectionEvent(GridSpace2DNode<K, O> n1, GridSpace2DNode<K, O> n2, Space2DNodeIntersectionResult result) {
		
		Iterator<Space2DNodeIntersectionListener<K, O>> it = intersectionListeners.iterator();
		while(it.hasNext()) {
			it.next().nodesIntersection(n1, n2, result);
		}
	}

}
